//电子游戏“辐射4”中，任务“通向自由”要求玩家到达名为“Freedom Trail Ring”的金属表盘，并使用表盘拼写特定关键词才能开门。 
//
// 给定一个字符串 ring，表示刻在外环上的编码；给定另一个字符串 key，表示需要拼写的关键词。您需要算出能够拼写关键词中所有字符的最少步数。 
//
// 最初，ring 的第一个字符与12:00方向对齐。您需要顺时针或逆时针旋转 ring 以使 key 的一个字符在 12:00 方向对齐，然后按下中心按钮，
//以此逐个拼写完 key 中的所有字符。 
//
// 旋转 ring 拼出 key 字符 key[i] 的阶段中： 
//
// 
// 您可以将 ring 顺时针或逆时针旋转一个位置，计为1步。旋转的最终目的是将字符串 ring 的一个字符与 12:00 方向对齐，并且这个字符必须等于字符
// key[i] 。 
// 如果字符 key[i] 已经对齐到12:00方向，您需要按下中心按钮进行拼写，这也将算作 1 步。按完之后，您可以开始拼写 key 的下一个字符（下一阶段
//）, 直至完成所有拼写。 
// 
//
// 示例： 
//
// 
//
//
// 
//
// 
//输入: ring = "godding", key = "gd"
//输出: 4
//解释:
// 对于 key 的第一个字符 'g'，已经在正确的位置, 我们只需要1步来拼写这个字符。 
// 对于 key 的第二个字符 'd'，我们需要逆时针旋转 ring "godding" 2步使它变成 "ddinggo"。
// 当然, 我们还需要1步进行拼写。
// 因此最终的输出是 4。
// 
//
// 提示： 
//
// 
// ring 和 key 的字符串长度取值范围均为 1 至 100； 
// 两个字符串中都只有小写字符，并且均可能存在重复字符； 
// 字符串 key 一定可以由字符串 ring 旋转拼出。 
// 
// Related Topics 深度优先搜索 广度优先搜索 字符串 动态规划 
// 👍 223 👎 0


package leetcode.editor.cn.lc514;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.concurrent.atomic.AtomicInteger;

public class FreedomTrail{
    public static void main(String[] args){
        Solution solution = new Solution();
        String ring = "caotmcaataijjxi";
        String key = "oatjiioicitatajtijciocjcaaxaaatmctxamacaamjjx";

        System.out.println("key.len = " + key.length());

        int rotateSteps = solution.findRotateSteps(ring, key);
        System.out.println("rotateSteps = " + rotateSteps);
    }
}
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {

    private Map<Character, List<Integer>> ringCharMap;
    private char[] keyChars;
    private char[] ringChars;
    private Map<Integer, Integer> leastStepMap = new HashMap<>();


    public int findRotateSteps(String ring, String key) {
        ringCharMap = buildCharIndexMap(ring);
        AtomicInteger min = new AtomicInteger(Integer.MAX_VALUE);
        keyChars = key.toCharArray();
        ringChars = ring.toCharArray();

        return leastSteps(0, 0);
//        steps(0, 0,0,min);
//        return min.get();
    }

    private int leastSteps(int keyIndex, int ringIndex) {
        if (keyIndex >= keyChars.length) {
            return 0;
        }
        Integer leastStep = getLeastStep(keyIndex, ringIndex);
        if (leastStep != null) {
            return leastStep;
        }
        leastStep = Integer.MAX_VALUE;
        char keyChar = keyChars[keyIndex];
        char ringChar = ringChars[ringIndex];
        if (keyChar == ringChar) {
            leastStep = leastSteps(keyIndex+1, ringIndex) +1;
        }else {
            List<Integer> indexes = ringCharMap.get(keyChar);
            for (Integer index : indexes) {
                int distance = getDistance(ringIndex, index);
                int least = leastSteps(keyIndex + 1, index) + distance + 1;
                leastStep = Math.min(leastStep, least);
            }
        }
        setLeastStep(keyIndex, ringIndex, leastStep);

        return leastStep;
    }

    private Integer getLeastStep(int keyIndex, int ringIndex) {
        int i = keyIndex << 10 | ringIndex;
        return leastStepMap.get(i);
    }

    private Integer setLeastStep(int keyIndex, int ringIndex,int leastStep) {
        int i = keyIndex << 10 | ringIndex;
        return leastStepMap.put(i,leastStep);
    }


    private void steps(int keyIndex, int ringIndex, int stepCount, AtomicInteger min) {

//        System.out.printf("ring:[%d], key:[%d], steps:%d, min:%d \n",ringIndex,keyIndex,stepCount,min.get());
//
//        if (keyIndex >= keyChars.length) {
//            if (stepCount < min.get()) {
//                min.set(stepCount);
//            }
//            return;
//        }
//        char keyChar = keyChars[keyIndex];
//        char ringChar = ringChars[ringIndex];
//        if (keyChar == ringChar) {
//            steps(keyIndex+1, ringIndex, stepCount+1, min);
//            return;
//        }
//
//        List<Integer> idxs = ringCharMap.get(keyChar);
//        for (Integer idx : idxs) {
//            int distance = getDistance(ringChars, ringIndex, idx);
//            steps(keyIndex+1, idx, stepCount+distance+1, min);
//        }
    }

    private int getDistance(int ringIndex, Integer idx) {
        int big = Math.max(ringIndex, idx);
        int small = Math.min(ringIndex, idx);
        return Math.min(big - small, ringChars.length + small - big);
    }

    private Map<Character, List<Integer>> buildCharIndexMap(String ring) {
        Map<Character, List<Integer>> characterMap = new HashMap<>();
        char[] charArray = ring.toCharArray();
        for (int i = 0, charArrayLength = charArray.length; i < charArrayLength; i++) {
            char c = charArray[i];
            int finalI = i;
            characterMap.compute(c, (ch, list) -> {
                if (list == null) {
                    list = new ArrayList<>();
                }
                list.add(finalI);
                return list;
            });
        }
        return characterMap;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

